Systems for sharing information such as traffic information among a plurality of vehicles using vehicle-to-vehicle communication are being studied and developed. When information possessed by a vehicle is transmitted to surrounding vehicles, the surrounding vehicles store the received information and further transmit the information to its surrounding vehicles. Information spreads in this manner.
In information sharing technology including, but not limited to, vehicle-to-vehicle communication, there are demands for sharing information in an efficient manner. For example, it is desirable to transmit information that is not possessed by a communication partner. However, with the increase in storage capacity of information devices, the number of pieces of data possessed by one communication node becomes enormous. When the number of pieces of data is large, determining what kind of data is possessed and what kind of data is not possessed by a communication partner becomes difficult.
A Bloom Filter is a known technique for detecting identity of data (Non-Patent Document 1). A Bloom Filter calculates hash values of data and overlaps obtained hash values on each other using a bit-wise OR operation. When a hash value of data to be checked is calculated and the filter has a value of 0 at any bit position, it is guaranteed that the data is not registered. A Bloom Filter enables an inspection to be performed instantaneously (at O(1)).
Therefore, it is conceivable to utilize a Bloom Filter in information sharing technique to efficiently spread information. In other words, it is conceivable to acquire a filter value of a Bloom Filter from a communication partner node and, using the filter value, select and transmit data that is not possessed by the partner. However, a Bloom Filter is limited in that, once registered, data cannot be deleted. As the period of use becomes longer, a probability of occurrence of erroneous determinations (determinations of non-possessed data to be possessed data, i.e. false positive) gradually increases. Therefore, it is not effective to apply a Bloom Filter to a system which information is constantly supplied to and mush be discarded from.